//https://leetcode.cn/problems/maximum-sum-queries/submissions/482922596/?envType=daily-question&envId=2023-11-17


const int N = 1e5 + 5;
struct Node
{
    int l, r;
    int x;
}tr[N * 4];

void pushup(int u)
{
    tr[u].x = max(tr[u << 1].x, tr[u << 1 | 1].x);
}

void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, -1};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void update(int u, int l, int r, int d)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].x = max(tr[u].x, d);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) update(u << 1, l, r, d);
        if(r > mid) update(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        return tr[u].x;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        int res = -1;
        if(l <= mid) res = query(u << 1, l, r);
        if(r > mid) res = max(res, query(u << 1 | 1, l, r));
        return res;
    }
}

class Solution
{
public:
    vector<int> nums;

    int get(int x)
    {
        auto pos = lower_bound(nums.begin(), nums.end(), x);
        if(pos != nums.end()) return pos - nums.begin() + 1;
        return -1;
    }

    vector<int> maximumSumQueries(vector<int> &nums1, vector<int> &nums2, vector<vector<int>> &queries)
    {
        nums = nums2;
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        int n = nums.size();
        build(1, 1, n);

        vector<pair<int, int>> v;
        vector<int> ans(queries.size());
        for(int i = 0; i < nums1.size(); i++) v.push_back({nums1[i], nums2[i]});
        sort(v.rbegin(), v.rend());
        for(int i = 0; i < queries.size(); i++) queries[i].push_back(i);
        sort(queries.rbegin(), queries.rend());

        int i = 0;
        for(const auto &q:queries)
        {
            int x = q[0], y = q[1], id = q[2];
            for(; i < v.size() && v[i].first >= x; i++)
            {
                int sum = v[i].first + v[i].second;
                int idx = get(v[i].second);
                update(1, idx, idx, sum);
            }
            int pos = get(y);
            if(pos == -1) ans[id] = -1;
            else ans[id] = query(1, pos, n);
        }
        return ans;
    }
};